package _06_动态规划;

public class _221_最大正方形 {

    public static void main(String[] args) {

        _221_最大正方形 v = new _221_最大正方形();

        /*char[][] ins = {
                {'1', '0', '1', '0', '0'},
                {'1', '0', '1', '1', '1'},
                {'1', '1', '1', '1', '1'},
                {'1', '0', '0', '1', '0'},
        };*/

        char[][] ins = {
                {'1', '1', '1', '1', '0'},
                {'1', '1', '1', '1', '0'},
                {'1', '1', '1', '1', '1'},
                {'1', '1', '1', '1', '1'},
                {'0', '0', '1', '1', '1'},
        };

       /* char[][] ins = {
                {'0', '1'},
                {'1', '0'},
        };*/

        System.out.println(v.maximalSquare(ins));
    }

    public int maximalSquare(char[][] matrix) {
        int row = matrix.length;
        int col = matrix[0].length;
        int width = Math.min(row, col);
        boolean[][] dp = new boolean[row * col][width + 1];
        // 初始化dp数据
        int max = 0;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                dp[i * col + j][1] = matrix[i][j] == '1';
                if (dp[i * col + j][1]) {
                    max = 1;
                }
            }
        }
        if (max == 0) return 0;
        // 遍历数据
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                int temp = Math.min(i, j) + 1;
                for (int k = 2; k <= temp; k++) {
                    dp[i * col + j][k] = matrix[i][j] == '1' && dp[i * col + j - 1][k - 1] && dp[(i - 1) * col + j][k - 1] && dp[(i - 1) * col + j - 1][k - 1];
                    if (dp[i * col + j][k]) {
                        max = Math.max(k * k, max);
                    }
                }
            }
        }
        return max;
    }

}
